package day_2022_4_to_7.day48;

import java.util.HashMap;
import java.util.Map;

/**
 * 最近公共祖先
 * （满二叉树中）
 * @author haomin
 * @date 2022/05/06 21:27
 **/
public class Day11_1_NearestCommonAncestor {
    public static void main(String[] args) {
        System.out.println(getLCA(3,8));
        System.out.println(getLCA1(3,8));
        System.out.println(getLCA2(3,8));
    }

    // 方法一 使用map
    public static int getLCA(int a, int b) {
        if(a == b){
            return a;
        }

        Map<Integer,Integer> map = new HashMap<>();
        while (a !=0){
            map.put(a,1);
            a = a/2;
        }

        while (b != 0){
            if(map.containsKey(b)){
                return b;
            }else {
                map.put(b,1);
            }
            b = b/2;
        }
        return 0;
    }

    // 方法二
    public static int getLCA1(int a, int b) {
        while (a != 0){
            int b1 = b;
            while (b1 != 0){
                if(a == b1){
                    return a;
                }
                b1 = b1/2;
            }
            a = a/2;
        }
        return 0;
    }

    // 方法三
    public static int getLCA2(int a, int b) {
        while (a != b){
            if(a > b){
                a = a/2;
            }else {
                b = b/2;
            }
        }
        return a;
    }
}